package org.example;

public class Main {
    // 1、无头单向非循环链表实现
    public class SingleLinkedList {
        private static class ListNode {
            int val;
            ListNode next;
            public ListNode(int val) {
                this.val = val;
                this.next = null;
            }
        }
        private ListNode head;
        private int size;
        //头插法
        public void addFirst(int data){
            ListNode newNode = new ListNode(data);
            newNode.next = head;
            head = newNode;
            size++;
        }
        //尾插法
        public void addLast(int data){
            ListNode newNode = new ListNode(data);
            if (head == null) {
                head = newNode;
            } else {
                // 找到最后一个节点
                ListNode cur = head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = newNode;
            }
            size++;
        }
        //任意位置插入,第一个数据节点为0号下标
        public boolean addIndex(int index,int data){
            if (index < 0 || index > size) {
                return false;
            }
            if (index == 0) {
                addFirst(data);
                return true;
            }
            if (index == size) {
                addLast(data);
                return true;
            }
            ListNode prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            ListNode newNode = new ListNode(data);
            newNode.next = prev.next;
            prev.next = newNode;
            size++;
            return true;
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
            if (head == null) {
                return;
            }

            // 头节点就是要删除的节点
            if (head.val == key) {
                head = head.next;
                size--;
                return;
            }

            // 寻找要删除节点的前一个节点
            ListNode prev = head;
            while (prev.next != null && prev.next.val != key) {
                prev = prev.next;
            }

            // 如果找到要删除的节点
            if (prev.next != null) {
                prev.next = prev.next.next;
                size--;
            }
        }
        //删除所有值为key的节点
        public void removeAllKey(int key){
            if (head == null) {
                return;
            }
            while (head != null && head.val == key) {
                head = head.next;
                size--;
            }
            if (head == null) {
                return;
            }
            ListNode prev = head;
            while (prev.next != null) {
                if (prev.next.val == key) {
                    prev.next = prev.next.next;
                    size--;
                } else {
                    prev = prev.next;
                }
            }
        }
        //得到单链表的长度
        public int size(){
            return size;
        }
        public void display(){
            ListNode cur = head;
            while (cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }
        public void clear(){
            while (head != null) {
                ListNode next = head.next;
                head.next = null;
                head = next;
            }
            size = 0;
        }
    }
    // 2、无头双向链表实现
    public class LinkedList {
        private static class ListNode {
            int val;
            ListNode prev;
            ListNode next;
            public ListNode(int val) {
                this.val = val;
                this.prev = null;
                this.next = null;
            }
        }

        private ListNode head;
        private ListNode tail;
        private int size;

        //头插法
        public void addFirst(int data){
            ListNode newNode = new ListNode(data);
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                newNode.next = head;
                head.prev = newNode;
                head = newNode;
            }
            size++;
        }
        //尾插法
        public void addLast(int data){
            ListNode newNode = new ListNode(data);
            if (tail == null) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                newNode.prev = tail;
                tail = newNode;
            }
            size++;
        }
        //任意位置插入,第一个数据节点为0号下标
        public boolean addIndex(int index,int data){

            if (index < 0 || index > size) {
                return false;
            }

            if (index == 0) {
                addFirst(data);
                return true;
            }


            if (index == size) {
                addLast(data);
                return true;
            }

            ListNode cur;

            if (index < size / 2) {
                cur = head;
                for (int i = 0; i < index; i++) {
                    cur = cur.next;
                }
            } else {
                cur = tail;
                for (int i = size - 1; i > index; i--) {
                    cur = cur.prev;
                }
            }

            ListNode newNode = new ListNode(data);
            newNode.prev = cur.prev;
            newNode.next = cur;
            cur.prev.next = newNode;
            cur.prev = newNode;
            size++;
            return true;
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
            if (head == null) {
                return;
            }
            ListNode cur = head;
            while (cur != null && cur.val != key) {
                cur = cur.next;
            }
            if (cur == null) {
                return;
            }
            if (cur == head) {
                head = head.next;
                if (head == null) {
                    tail = null;
                } else {
                    head.prev = null;
                }
            }
            else if (cur == tail) {
                tail = tail.prev;
                tail.next = null;
            }
            else {
                cur.prev.next = cur.next;
                cur.next.prev = cur.prev;
            }

            size--;
        }
        //删除所有值为key的节点
        public void removeAllKey(int key){
            if (head == null) {
                return;
            }
            ListNode cur = head;
            while (cur != null) {
                ListNode next = cur.next;
                if (cur.val == key) {
                    if (cur == head) {
                        head = head.next;
                        if (head != null) {
                            head.prev = null;
                        } else {
                            tail = null;
                        }
                    }
                    else if (cur == tail) {
                        tail = tail.prev;
                        tail.next = null;
                    }
                    else {
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                    size--;
                }
                cur = next;
            }
        }
        //得到单链表的长度
        public int size(){
            return size;
        }
        public void display() {
            ListNode cur = head;
            while (cur != null) {
                System.out.print(cur.val + " ");
                cur = cur.next;
            }
            System.out.println();
        }
        public void clear() {
            ListNode cur = head;
            while (cur != null) {
                ListNode next = cur.next;
                cur.prev = null;
                cur.next = null;
                cur = next;
            }
            head = null;
            tail = null;
            size = 0;
        }
    }

    public ListNode partition(ListNode pHead, int x) {
        if (pHead == null) {
            return null;
        }

        ListNode smallHead = new ListNode(0);
        ListNode largeHead = new ListNode(0);
        ListNode small = smallHead;
        ListNode large = largeHead;
        while (pHead != null) {
            if (pHead.val < x) {
                small.next = pHead;
                small = small.next;
            } else {
                large.next = pHead;
                large = large.next;
            }
            pHead = pHead.next;
        }
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }

    public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            if (A == null || A.next == null) {
                return true;
            }

            ListNode slow = A;
            ListNode fast = A;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode secondHalf = reverseList(slow.next);
            ListNode firstHalf = A;
            while (secondHalf != null) {
                if (firstHalf.val != secondHalf.val) {
                    return false;
                }
                firstHalf = firstHalf.next;
                secondHalf = secondHalf.next;
            }
            return true;
        }
        private ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null) {
                ListNode nextTemp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }
    }

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            ListNode pA = headA;
            ListNode pB = headB;
            while (pA != pB) {
                pA = (pA == null) ? headB : pA.next;
                pB = (pB == null) ? headA : pB.next;
            }
            return pA;
        }
    }

    public class solution {
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null) {
                return false;
            }

            ListNode slow = head;
            ListNode fast = head.next;

            while (slow != fast) {
                if (fast == null || fast.next == null) {
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    }

    public class Solution2 {
        public ListNode detectCycle(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
            boolean hasCycle = false;

            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast) {
                    hasCycle = true;
                    break;
                }
            }

            if (!hasCycle) {
                return null;
            }

            ListNode ptr1 = head;
            ListNode ptr2 = slow;

            while (ptr1 != ptr2) {
                ptr1 = ptr1.next;
                ptr2 = ptr2.next;
            }

            return ptr1;
        }
    }

    class Solution3 {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode dummy = new ListNode(-1);
            ListNode current = dummy;

            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    current.next = list1;
                    list1 = list1.next;
                } else {
                    current.next = list2;
                    list2 = list2.next;
                }
                current = current.next;
            }

            current.next = (list1 != null) ? list1 : list2;
            return dummy.next;
        }
    }
    public static void main(String[] args) {

    }
}